package org.niu.interval;

import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;
import java.util.PriorityQueue;

public class Merge {
    public ArrayList<Interval> merge(ArrayList<Interval> intervals) {
        ArrayList<Interval> ans = new ArrayList<>();
        PriorityQueue<Interval> q = new PriorityQueue<>(new Comparator<Interval>() {
            @Override
            public int compare(Interval o1, Interval o2) {
                if(o1.start!=o2.start){
                    return o1.start-o2.start;
                }
                return o1.end-o2.end;
            }
        });
        for (Interval interval : intervals) {
            q.offer(interval);
        }
        while(q.size()>=2){
            Interval p1 = q.poll();
            Interval p2 = q.poll();
            if(p1.end<p2.start){
                ans.add(p1);
                q.offer(p2);
            }else{
                q.offer(new Interval(p1.start,Math.max(p1.end,p2.end)));
            }
        }
        if(!q.isEmpty()){
            ans.add(q.poll());
        }
        return ans;
    }
}
